#include "../tools.h"



class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b){
        return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
    }
    vector<vector<int>> pick(const vector<vector<int>>& envelopes){
        int i = 0, size = envelopes.size(), j;
        vector<vector<int>> res;
        int maxe = -1;
        while(i < size){
            maxe = envelopes[i][1];
            j = i + 1;
            while(j < size && envelopes[i][0] == envelopes[j][0]){
                if(envelopes[j][1] > maxe) maxe = envelopes[j][1];
                ++j;
            }
            res.push_back({envelopes[i][0], maxe});
            i = j;
        }
        // show(envelopes);
        // cout << endl;
        // show(res);
        // cout << endl;
        return res;
    }
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if(envelopes.size() == 0) return 0;
        if(envelopes.size() == 1) return 1;

        sort(envelopes.begin(), envelopes.end(), cmp);
        // envelopes = pick(envelopes);

        show(envelopes);
        vector<int> tail;
        tail.push_back(envelopes[0][1]);
        for(int i = 1; i < envelopes.size(); ++i){
            if(envelopes[i][1] > tail.back()) tail.push_back(envelopes[i][1]);
            else{
                auto p = lower_bound(tail.begin(), tail.end(), envelopes[i][1]);
                *p = envelopes[i][1];
            }
        }


        return tail.size();
    }
};

int main(int argc, char const *argv[])
{
    Solution sol;

    // vector<vector<int>> envelopes = {{5,4},{6,4},{6,7},{2,3}};
    // vector<vector<int>> envelopes = {{1,1},{1,1},{1,1}};
    vector<vector<int>> envelopes = {{4,5},{4,6},{6,7},{2,3},{1,1}};
    // vector<vector<int>> envelopes = {{1,2},{2,3},{3,4},{3,5},{4,5},{5,5},{5,6},{6,7},{7,8}};
    
    int res = sol.maxEnvelopes(envelopes);
    cout << res << endl;

    return 0;
}
